package com.yanceysong.codetop.s71_s80;


public class S79_Mid_221_最大正方形 {
    /**
     * .S79_Mid_221_最大正方形
     * .<p>
     * .<a href="https://leetcode.cn/problems/maximal-square/">...</a>
     * .<p>
     * .题目：在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
     * .<p>
     * .示例：
     * .输入：
     * .[
     * .  ["1","0","1","0","0"],
     * .  ["1","0","1","1","1"],
     * .  ["1","1","1","1","1"],
     * .  ["1","0","0","1","0"]
     * .]
     * .输出：4
     * .解释：最大的只包含'1'的正方形边长为2，面积为2*2=4。
     * .<p>
     * .核心标签：动态规划、矩阵
     * .<p>
     * .思路（DP）：
     * .- 定义 maxLenAt[row][col] 表示以坐标 (row, col) 为右下角的、只包含 '1' 的最大正方形的边长。
     * .- 转移：当 matrix[row][col] == '1' 时，
     * .  maxLenAt[row][col] = min(maxLenAt[row-1][col], maxLenAt[row][col-1], maxLenAt[row-1][col-1]) + 1；否则为0（默认）。
     * .- 同时维护最大边长 largestSide，最终面积为 largestSide * .largestSide。
     * .<p>
     * .为什么取三个方向的最小值？ASCII图解：
     * .假设当前单元是 '1'，要把右下角扩展成更大的正方形，需要它的上方、左方、左上方都能支撑同样的正方形边长。
     * .只有三者的最小边长决定能扩展多少：
     * .  [row-1][col-1]  [row-1][col]
     * .  [row][col-1]    [row][col]
     * .其中 [row][col] 是当前单元。若上、左、左上的最大边长分别为 a、b、c，则当前能形成的最大边长为 min(a,b,c)+1。
     * .<p>
     * .边界：第一行或第一列，如果该位置是 '1'，则 maxLenAt[row][col]=1（无法从三方向扩展）。
     * .<p>
     * .时间复杂度：O(m*n)，m 为行数，n 为列数。
     * .空间复杂度：O(m*n)（可优化为 O(n) 使用滚动数组，但此处保留清晰版本）。
     * .<p>
     * .关键洞察：
     * .- “以某点为正方形右下角”的视角，让问题局部化，便于用前缀性质递推。
     * .- 当前为 '1' 且三邻域能形成的最小正方形边长 +1，即可形成更大正方形。
     * .- 只需一次遍历即可得到全局最大边长。
     */
    public int maximalSquare(char[][] matrix) {
        // 记录遍历过程中出现的最大正方形边长
        int largestSide = 0;

        // 边界处理：空矩阵或维度为0，直接返回面积0
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return largestSide; // 面积=0
        }

        // 行数与列数
        int rowCount = matrix.length;
        int colCount = matrix[0].length;

        // maxLenAt[row][col]：以 (row,col) 为右下角的只包含'1'的最大正方形边长
        int[][] maxLenAt = new int[rowCount][colCount];

        // 遍历每个单元格，按从上到下、从左到右的顺序
        for (int row = 0; row < rowCount; row++) {
            for (int col = 0; col < colCount; col++) {
                if (matrix[row][col] == '1') {
                    if (row == 0 || col == 0) {
                        // 第一行或第一列，只要是'1'，最大边长就是1
                        maxLenAt[row][col] = 1;
                    } else {
                        // 状态转移：取上、左、左上三者的最小值再 +1
                        // 上方:   maxLenAt[row-1][col]
                        // 左方:   maxLenAt[row][col-1]
                        // 左上方: maxLenAt[row-1][col-1]
                        maxLenAt[row][col] = Math.min(
                                Math.min(maxLenAt[row - 1][col], maxLenAt[row][col - 1]),
                                maxLenAt[row - 1][col - 1]
                        ) + 1;
                    }
                    // 更新全局最大边长
                    largestSide = Math.max(largestSide, maxLenAt[row][col]);
                }
                // 若当前是 '0'，maxLenAt[row][col] 默认是0，无需赋值
            }
        }
        // 返回最大面积 = 最大边长的平方
        return largestSide * largestSide;
    }

    // ========================= 测试用例 =========================
    public static void main(String[] args) {
        S79_Mid_221_最大正方形 solution = new S79_Mid_221_最大正方形();

        System.out.println("=== 最大正方形测试开始 ===");

        // 测试1：题目示例（应返回4）
        System.out.println("\n--- 测试1：题目示例 ---");
        testLeetCodeExample(solution);

        // 测试2：单元素为'0'（应返回0）
        System.out.println("\n--- 测试2：单元素为'0' ---");
        testSingleZero(solution);

        // 测试3：单元素为'1'（应返回1）
        System.out.println("\n--- 测试3：单元素为'1' ---");
        testSingleOne(solution);

        // 测试4：全为'1'的 2x2 矩阵（应返回4）
        System.out.println("\n--- 测试4：2x2 全'1' ---");
        testAllOnes2x2(solution);

        // 测试5：全为'1'的 3x3 矩阵（应返回9）
        System.out.println("\n--- 测试5：3x3 全'1' ---");
        testAllOnes3x3(solution);

        // 测试6：非正方形矩阵（含'0'阻断）
        System.out.println("\n--- 测试6：非正方形含阻断 ---");
        testRectangularWithBlocks(solution);

        // 测试7：空矩阵
        System.out.println("\n--- 测试7：空矩阵 ---");
        testEmptyMatrix(solution);

        // 测试8：null 输入
        System.out.println("\n--- 测试8：null 输入 ---");
        testNullMatrix(solution);

        // 额外测试9：全为'0'的矩阵（应返回0）
        System.out.println("\n--- 测试9：全'0'矩阵 ---");
        testAllZeros(solution);

        // 额外测试10：单行矩阵（连续'1'）
        System.out.println("\n--- 测试10：单行连续'1' ---");
        testSingleRow(solution);

        // 额外测试11：单列矩阵（连续'1'）
        System.out.println("\n--- 测试11：单列连续'1' ---");
        testSingleColumn(solution);

        // 额外测试12：最大正方形在边界
        System.out.println("\n--- 测试12：边界上的最大正方形 ---");
        testBorderMaxSquare(solution);

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * .题目示例：期望4
     */
    private static void testLeetCodeExample(S79_Mid_221_最大正方形 solution) {
        char[][] matrix = new char[][]{
                {'1', '0', '1', '0', '0'},
                {'1', '0', '1', '1', '1'},
                {'1', '1', '1', '1', '1'},
                {'1', '0', '0', '1', '0'}
        };
        int area = solution.maximalSquare(matrix);
        System.out.println("matrix(示例) -> area = " + area + " (期望: 4)");
        assert area == 4 : "题目示例应返回4";
        System.out.println("✓ 题目示例通过");
    }

    /**
     * .单元素为'0'：期望0
     */
    private static void testSingleZero(S79_Mid_221_最大正方形 solution) {
        char[][] matrix = new char[][]{{'0'}};
        int area = solution.maximalSquare(matrix);
        System.out.println("[['0']] -> area = " + area + " (期望: 0)");
        assert area == 0 : "单'0'应返回0";
        System.out.println("✓ 单'0'通过");
    }

    /**
     * .单元素为'1'：期望1
     */
    private static void testSingleOne(S79_Mid_221_最大正方形 solution) {
        char[][] matrix = new char[][]{{'1'}};
        int area = solution.maximalSquare(matrix);
        System.out.println("[['1']] -> area = " + area + " (期望: 1)");
        assert area == 1 : "单'1'应返回1";
        System.out.println("✓ 单'1'通过");
    }

    /**
     * .2x2 全为'1'：期望4
     */
    private static void testAllOnes2x2(S79_Mid_221_最大正方形 solution) {
        char[][] matrix = new char[][]{
                {'1', '1'},
                {'1', '1'}
        };
        int area = solution.maximalSquare(matrix);
        System.out.println("2x2 all '1' -> area = " + area + " (期望: 4)");
        assert area == 4 : "2x2全'1'应返回4";
        System.out.println("✓ 2x2全'1'通过");
    }

    /**
     * .3x3 全为'1'：期望9
     */
    private static void testAllOnes3x3(S79_Mid_221_最大正方形 solution) {
        char[][] matrix = new char[][]{
                {'1', '1', '1'},
                {'1', '1', '1'},
                {'1', '1', '1'}
        };
        int area = solution.maximalSquare(matrix);
        System.out.println("3x3 all '1' -> area = " + area + " (期望: 9)");
        assert area == 9 : "3x3全'1'应返回9";
        System.out.println("✓ 3x3全'1'通过");
    }

    /**
     * .非正方形矩阵（含阻断）：期望最大为4
     */
    private static void testRectangularWithBlocks(S79_Mid_221_最大正方形 solution) {
        char[][] matrix = new char[][]{
                {'1', '1', '1', '1'},
                {'1', '1', '0', '1'},
                {'1', '1', '1', '1'}
        };
        int area = solution.maximalSquare(matrix);
        System.out.println("rect with block -> area = " + area + " (期望: 4)");
        assert area == 4 : "阻断导致最大边长为2，面积4";
        System.out.println("✓ 非正方形含阻断通过");
    }

    /**
     * .空矩阵：期望0
     */
    private static void testEmptyMatrix(S79_Mid_221_最大正方形 solution) {
        char[][] matrix = new char[0][]; // 行数为0
        int area = solution.maximalSquare(matrix);
        System.out.println("empty -> area = " + area + " (期望: 0)");
        assert area == 0 : "空矩阵应返回0";
        System.out.println("✓ 空矩阵通过");
    }

    /**
     * .null 输入：期望0
     */
    private static void testNullMatrix(S79_Mid_221_最大正方形 solution) {
        int area = solution.maximalSquare(null);
        System.out.println("null -> area = " + area + " (期望: 0)");
        assert area == 0 : "null应返回0";
        System.out.println("✓ null输入通过");
    }

    /**
     * .全为'0'的矩阵：期望0
     */
    private static void testAllZeros(S79_Mid_221_最大正方形 solution) {
        char[][] matrix = new char[][]{
                {'0', '0', '0'},
                {'0', '0', '0'},
                {'0', '0', '0'}
        };
        int area = solution.maximalSquare(matrix);
        System.out.println("3x3 all '0' -> area = " + area + " (期望: 0)");
        assert area == 0 : "全'0'应返回0";
        System.out.println("✓ 全'0'通过");
    }

    /**
     * .单行矩阵（连续'1'）：期望为最长连续'1'的平方, 但单行只能形成1x1，所以期望为1
     */
    private static void testSingleRow(S79_Mid_221_最大正方形 solution) {
        char[][] matrix = new char[][]{
                {'1', '1', '1', '1', '1'}
        };
        int area = solution.maximalSquare(matrix);
        System.out.println("single row '1's -> area = " + area + " (期望: 1)");
        assert area == 1 : "单行只能形成1x1正方形，面积1";
        System.out.println("✓ 单行连续'1'通过");
    }

    /**
     * .单列矩阵（连续'1'）：期望为1（同理单行）
     */
    private static void testSingleColumn(S79_Mid_221_最大正方形 solution) {
        char[][] matrix = new char[][]{
                {'1'},
                {'1'},
                {'1'},
                {'1'}
        };
        int area = solution.maximalSquare(matrix);
        System.out.println("single column '1's -> area = " + area + " (期望: 1)");
        assert area == 1 : "单列只能形成1x1正方形，面积1";
        System.out.println("✓ 单列连续'1'通过");
    }

    /**
     * .最大正方形在边界：确保边界处理正确
     */
    private static void testBorderMaxSquare(S79_Mid_221_最大正方形 solution) {
        char[][] matrix = new char[][]{
                {'1', '1', '1'},
                {'1', '1', '1'},
                {'0', '0', '0'}
        };
        int area = solution.maximalSquare(matrix);
        System.out.println("border max square -> area = " + area + " (期望: 4)");
        assert area == 4 : "上方2x2正方形在边界，面积4";
        System.out.println("✓ 边界最大正方形通过");
    }
}
